Feature #3: Balloon Splash

Implementing the "Balloon Splash" feature for our "Language Compiler" project.

Description#

We have to develop the game named Balloon Splash. Assume that there are multiple colored balloons, and we have to shoot a column of balloons of the same color. We can only splash k consecutive balloons of the same color. Once a set of k consecutive balloons is splashed, any balloons above it will fall to replace them. We will keep shooting until it is not possible to shoot k consecutive balloons of the same color. In the end, there will not be any k consecutive balloons left. For this problem, our input will be in the form of the English alphabet. Each letter will represent a unique colored balloon.

Let’s go through the following illustration to understand this problem:

a
a
s
s
s
s
s
s
a
a
d
d
d
d
k
k
k
k
k
k
d
d
a
a
s
s
k = 3
k = 3
a
a
a
a
d
d
d
d
d
d
a
a
s
s
a
a
a
a
a
a
s
s
s
s
Viewer does not support full SVG 1.1
k consecutive balloons

Solution#

We are given a string str and an integer k, where the k consecutive letters that are identical can be eliminated from the string str. After removing the k consecutive occurrences of the same letter, we have to concatenate the remaining substrings together.

Here is how we will implement this feature:

  • We will use a stack to maintain the count of adjacent duplicates.

  • If the current character is the same as the previous one, we will increment the count on the top of the stack. Otherwise, we will push 1 along with the character to the stack.

  • Next, we will check if the count on the top of the stack reaches k, and then perform the pop operation.

  • We will iterate on the given string str until we reach the last character of the string.

Let’s see the following illustrations to understand this solution.

At the left, the given set of balloons is shown. Then, consecutive sets of 3 identical balloons are splashed repeatedly from left to right

Created with Fabric.js 3.6.6
Find k consecutive characters

1 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

2 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

3 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

4 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

5 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

6 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

7 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

8 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

9 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

10 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

11 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

12 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

13 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

14 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

15 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

16 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

17 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

18 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

19 of 20

Created with Fabric.js 3.6.6
Find k consecutive characters

20 of 20

Let’s look at the solution code below:

Remove the k consecutive characters

Complexity measures#

Time complexity Space complexity
O(n)O(n) O(n)O(n)

Time complexity#

We will iterate over all the nn characters of the given string exactly once. For each character, we will perform O(1)O(1) operations. Therefore, the time complexity will be O(n)O(n) in the worst-case scenario.

Space complexity#

The space complexity will be O(n)O(n) in the worst-case scenario, when the stack will contain all the characters with their size.

Feature #2: Maximum Points You Can Obtain from Cards

What Did We Learn?